#!/usr/bin/env python
#-*- coding: utf-8 -*-
#__author__:vincentlc
#time: 16/5/29 : 17:20

'''
Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
'''
from functools import reduce

class Solution(object):
    def trailingZeroes(self, n):
        """
        :type n: int
        :rtype: int
        """
        factorial_num = reduce(lambda x,y:x*y,range(1,n+1))
        count = 0
        for i in list(str(factorial_num)):
            if i =='0':
                count+=1
        return count
    
    def trailingZeroes2(self, n):
        x = 5
        ans = 0
        while n >= x:
            ans += n / x
            x *= 5
        return ans


cls_a = Solution()
print(cls_a.trailingZeroes(4807))
# print(cls_a.trailingZeroes(4807))
